import java.util.Deque;
import java.util.LinkedList;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/12
 * \* Time: 15:51
 * \* To change this template use File | Settings | File Templates.
 * \* Description:请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
 *
 * 若队列为空，pop_front 和 max_value需要返回 -1
 *题解：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/solution/ru-he-jie-jue-o1-fu-za-du-de-api-she-ji-ti-by-z1m/
 * \
 */
public class 队列的最大值II {
    Deque<Integer> res,max;

    public void MaxQueue() {
        res = new LinkedList<Integer>();
        max = new LinkedList<Integer>();
    }

    public int max_value() {
        if(max.isEmpty()) {
            return -1;
        }
        return max.peekFirst();
    }

    public void push_back(int value){
        res.addLast(value);
        while (!max.isEmpty()&&max.peekLast()<value){
            max.removeLast();
        }
        max.addLast(value);
    }

    public int pop_front(){
        if(res.isEmpty()){
            return -1;
        }
        int tmp=res.peekFirst();
        if(tmp==max.peekFirst()){
            max.removeFirst();
        }
        res.removeFirst();
        return  tmp;
    }
}